1. Technical Field
This disclosure relates generally to memory management in a data processing system and more specifically to compaction planning in a memory manager of the data processing system.
2. Description of the Related Art
A memory management system, which does not move objects, may be affected by memory fragmentation. One typical mechanism for resolving memory fragmentation is compaction.
Abuaiadh et al (Abuaiadh, Ossia, Petrank and Silbershtein, “An efficient parallel heap compaction algorithm”, Proceedings of the 19th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, 2004) described, at the time, a state of the art compactor which is currently used in IBM® Java® Virtual Machines (IBM is a registered trademark of IBM in the United States, other countries or both; Java and all Java-based trademarks and logos are trademarks or registered trademarks of Oracle and/or its affiliates). The compactor uses a small amount of auxiliary storage, and claims to achieve “(almost) perfect compaction”. However, in practice, “perfection” of the compaction typically decreases as parallelism increases. Each compactor thread must lock an associated destination area while the compactor thread evacuates into the respective destination area. While the respective destination area is locked, the area is not eligible to be an evacuation destination for other compactor threads, and the other compactor threads by-pass locked destination area and select a next available destination. The compactor may, therefore, leave some fragmentation as destination areas may become incompletely consumed.
Kermany and Petrank (Kermany and Petrank, “The Compressor: Concurrent, Incremental, and Parallel Compaction”, PLDI'06, pp. 354-363, 2006) recently disclosed an advance in compactor design, which improves upon the compactor of Abuaiadh et al. The stop-the-world compactor of Kermany and Petrank divides compaction into two phases, which may be referred to as term “plan” and “move.” During a planning phase, a new location of each object (or group of objects) is determined and recorded in a concise manner in an offset table. Once planning is complete, the data in a mark vector and the offset table can be combined to determine a destination of any object. The determination capability allows the move phase to move objects to predetermined destinations and fix up associated references to other objects at the same time. Thus the move phase is the only phase of the compactor, which reads or writes the heap. Planning and external fix-up do not need to read or write heap memory. The collector of Kermany and Petrank also includes a concurrent and incremental aspect, which is not considered in the present disclosure.
The plan task in the compactor of Kermany and Petrank is single threaded. While this does result in optimal planning, the single thread is typically a performance bottleneck. Kermany and Petrank claim the plan task can be parallelized using “simple tricks”, but the tricks are not described nor do they describe the optimality of the resulting plan. Those skilled in the art of implementing parallel planning typically view parallelizing the planning stage as more than a simple trick involving non-obvious algorithms. For example, a simple solution mimics the algorithm used by Abuaiadh et al. However this results in suboptimal planning, with the problem becoming worse as parallelism increases.
In another prior example, a system designates each segregated area as the responsibility of a single thread and does not deal with cross-region compaction to provide ideal compaction. Further, the system is directed toward solving a problem of references between the segregated areas and how to track the areas thereby treating inter-region references different from references within the same region.
Another example system describes how to choose pages for compaction and relocate objects concurrently. The example system needs to perform reference fix-up operations. Optimizing object reference fix-up is typically an expensive part of a compaction operation in a garbage collected heap as is using thread locks.
Another prior example of a system deals primarily with how to determine and store information corresponding to pre-compaction location and size of a set of objects in a given extent of a heap (as well as how to avoid moving “dense prefixes” of objects).
In another example, a system relies on building a static dependency graph between blocks, which requires a pass to realize and build the dependency graph. Building the dependency graph typically causes a minimal set of concrete dependencies to be found (with few enough threads or a sufficiently shallow plan, it is possible for no thread to ever be blocked on another: thus, no dependencies are discovered). Secondly, the algorithm used in the example system requires single-threaded copying into a given destination block. Further, the algorithm typically relies on being able to slide objects to lower blocks in the address space, which creates unavoidable contention points in the dependency graph. There is therefore a need for a more effective compaction planning mechanism.